package DynamicProgramming;

public class _338_CountingBits {
    //first solution,divide 2
    public int[] countBits(int num) {
        int counts[] = new int[num+1];
        for(int i=0;i<=num;i++) {
            counts[i] = getBits(i);
        }
        return counts;
    }

    public int getBits(int n) {
        int count = 0;
        while (n != 0) {
            if (n % 2 == 1) {
                count++;
            }
            n/=2;
        }
        return count;
    }

    //second solution,use dynamic programming method
    //Principle:if a%2 = 0, a is like a/2's every bit go right 1 bit,so none bit is generate,
    //if a%2 !=0,it's clear that a/2 go right and add a 1,so bit count +1
    public int[] countBits1(int num) {
        if (num == 0) {
            int[] ch = {0};
            return ch;
        } else if (num == 1) {
            int[] ch = {0, 1};
            return ch;
        } else {
            int[] ch = new int[num + 1];
            ch[0] = 0;
            ch[1] = 1;
            ch[2] = 1;
            for(int i=3;i<=num;i++) {
                int temp = i%2;
                if (temp == 0) {
                    ch[i] = ch[i/2];
                } else {
                    ch[i] = 1 + ch[i/2];
                }
            }
            return ch;
        }
    }

    //solution 2's clear and easy pattern
    public int[] countBits2(int num) {
        int[] dp = new int[num+1];
        for (int i = 1; i <= num; i++) {
            dp[i] = dp[i>>1] + (i & 1);
        }
        return dp;
    }
}
